package com.lw.leetcode.binary.c;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * c
 * bainy
 * 1970. 你能穿过矩阵的最后一天
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/30 10:03
 */
public class LatestDayToCross {

    public static void main(String[] args) {

        LatestDayToCross test = new LatestDayToCross();

        // 2
//        int row = 2;
//        int col = 2;
//        int[][] cells = {{1, 1}, {2, 1}, {1, 2}, {2, 2}};

        // 1
//        int row = 2;
//        int col = 2;
//        int[][] cells = {{1, 1}, {1, 2}, {2, 1}, {2, 2}};

        // 3
//        int row = 3;
//        int col = 3;
//        int[][] cells = {{1, 2}, {2, 1}, {3, 3}, {2, 2}, {1, 1}, {1, 3}, {2, 3}, {3, 2}, {3, 1}};

        // 3
        int row = 32;
        int col = 3;
        int[][] cells = {{29,2},{14,2},{22,2},{26,3},{11,3},{6,2},{1,3},{26,2},{4,1},{19,2},{12,1},{9,3},{25,1},{31,3},{20,1},{9,2},{17,3},{28,3},{20,3},{17,2},{22,3},{27,1},{30,3},{4,2},{1,2},{14,3},{28,2},{11,1},{27,3},{32,3},{3,3},{29,1},{10,3},{28,1},{2,2},{24,2},{12,2},{29,3},{19,3},{16,1},{10,1},{27,2},{6,1},{25,3},{1,1},{13,2},{24,1},{23,2},{21,2},{15,2},{16,3},{20,2},{14,1},{3,2},{8,1},{4,3},{12,3},{7,1},{30,1},{3,1},{13,1},{18,1},{19,1},{6,3},{31,2},{11,2},{8,3},{2,3},{32,2},{23,1},{15,1},{16,2},{23,3},{30,2},{2,1},{25,2},{17,1},{7,2},{7,3},{26,1},{13,3},{18,3},{22,1},{21,3},{5,1},{10,2},{21,1},{32,1},{5,2},{24,3},{31,1},{9,1},{8,2},{15,3},{18,2},{5,3}};

        int i = test.latestDayToCross(row, col, cells);
        System.out.println(i);
    }

    private int[][] items = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int row;
    private int col;

    public int latestDayToCross(int row, int col, int[][] cells) {
        this.row = row;
        this.col = col;
        int[][] arr = new int[row][col];
        int st = 0;
        int end = row * col - 1;
        LinkedList<Long> list = new LinkedList<>();
        int step = 0;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            add(arr, cells, m);
            step = find(arr, list);
            if (step >= 0) {
                st = m;
            } else {
                end = m - 1;
            }
            fill(arr);
            list.clear();
        }
        if (step < 0) {
            add(arr, cells, st);
            step = find(arr, list);
            fill(arr);
        }
        return st + step;
    }

    private int find(int[][] arr, LinkedList<Long> list) {
        int[] ints = arr[0];
        int length = ints.length;
        for (int i = 0; i < length; i++) {
            int t = ints[i];
            if (t == 0) {
                list.add((long) i << 32);
                ints[i] = 1;
            }
        }
        while (!list.isEmpty()) {
            long p = list.poll();
            int x = (int) (p >> 48);
            int y = (int) ((p >> 32) & 0XFFFF);
            int step = (int) p + 1;
            for (int[] item : items) {
                int a = x + item[0];
                int b = y + item[1];
                if (a < 0 || b < 0 || a == row || b == col || arr[a][b] != 0) {
                    continue;
                }
                if (a == row - 1) {
                    return 0;
                }
                arr[a][b] = 1;
                list.add(((long) a << 48) + ((long) b << 32) + step);
            }
        }
        return -1;
    }

    private void add(int[][] arr, int[][] cells, int m) {
        for (int i = 0; i < m; i++) {
            int[] cell = cells[i];
            arr[cell[0] - 1][cell[1] - 1] = 1;
        }
    }

    private void fill(int[][] arr) {
        for (int[] ints : arr) {
            Arrays.fill(ints, 0);
        }
    }

}
